This work proposes a novel smoothing method, called Bend, Mix and Release (BMR), that extends two well-known smooth approximations of the convex optimization literature: randomized smoothing and the Moreau envelope. The BMR smoothing method allows to trade-off between the computational simplicity of randomized smoothing (RS) and the approximation efficiency of the Moreau envelope (ME). More specifically, we show that BMR achieves up to a $\sqrt{d}$ multiplicative improvement compared to the approximation error of RS, where $d$ is the dimension of the search space, while being less computation intensive than the ME. For non-convex objectives, BMR also has the desirable property to widen local minima, allowing optimization methods to reach small cracks and crevices of extremely irregular and non-convex functions, while being well-suited to a distributed setting. This novel smoothing method is then used to improve first-order non-smooth optimization (both convex and non-convex) by allowing for a local exploration of the search space.

Summary and Contributions: This paper describes a way to smooth functions that interpolates between the Moreau envelope and the "randomized sampling" smoothing which approximates a function f with fRS(x) E_z[f(x gamma z)] where is a standard Gaussian and gamma is a smoothing parameter. Such an approach is useful because many optimization methods only apply to smooth functions, but can be extended to nonsmooth functions with controlled error by using such smoothings. The key claimed drawback with random sampling is that it introduces an approximation error for a given level of smoothing that is dimension-dependent (on the order of sqrt(d)). The key claimed drawback with the Moreau envelope is that it is difficult to compute (as it involves solving an optimization problem). The proposed interpolation essentially replaces the minimization problem in the Moreau envelope with a "soft" approximation.

This work proposes a novel smoothing method, called Bend, Mix and Release (BMR), that extends two well-known smooth approximations of the convex optimization literature: randomized smoothing and the Moreau envelope. The BMR smoothing method allows to trade-off between the computational simplicity of randomized smoothing (RS) and the approximation efficiency of the Moreau envelope (ME). More specifically, we show that BMR achieves up to a \sqrt{d} multiplicative improvement compared to the approximation error of RS, where d is the dimension of the search space, while being less computation intensive than the ME. For non-convex objectives, BMR also has the desirable property to widen local minima, allowing optimization methods to reach small cracks and crevices of extremely irregular and non-convex functions, while being well-suited to a distributed setting. This novel smoothing method is then used to improve first-order non-smooth optimization (both convex and non-convex) by allowing for a local exploration of the search space.